package com.sicheng.lc.周赛.分类.思维.最大子段和;

import static java.lang.Math.max;
import static java.lang.Math.min;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/26 12:24
 */
public class 拼接数组的最大分数 {
    //todo
    //https://leetcode.cn/problems/maximum-score-of-spliced-array/
    int[] s1 = new int[10005], s2 = new int[10005], s = new int[10005];

    public int maximumsSplicedArray(int[] nums1, int[] nums2) {
        return max(maxSubArray(nums1, nums2), maxSubArray(nums2, nums1));
    }

    public int maxSubArray(int[] nums1, int[] nums2) {
        int pre = 0;
        int preSum = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums1.length; i++) {
            pre += nums1[i];
            int j = nums1[i] - nums2[i];
            if (preSum + j < j) {
                preSum = j;
            } else {
                preSum += j;
            }
            max = Math.max(max, preSum);
        }
        return pre + max;
    }

    // 汪乐平解法
    private int leetcode(int[] nums1, int[] nums2) {
        int n = nums1.length, i, m1, m2, ans;
        for (i = 0; i < n; i++) {
            s1[i + 1] = s1[i] + nums1[i];
            s2[i + 1] = s2[i] + nums2[i];
            s[i + 1] = s1[i] - s2[i];
        }
        ans = max(s1[n], s2[n]);
        for (i = m1 = m2 = 0; i <= n; i++) {
            m1 = max(m1, s[i]);
            m2 = min(m2, s[i]);
            ans = max(
                    ans,
                    max(
                            max(s1[n] - s[i] + m1, s2[n] + s[i] - m1),
                            max(s1[n] - s[i] + m2, s2[n] + s[i] - m2)
                    ));
        }
        return ans;
    }


}
